//剑指 Offer 53 - I. 在排序数组中查找数字 I
//https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/?favorite=xb9nqhhg
int search(int* nums, int numsSize, int target)
{
    if (numsSize == 0)
    {
        return 0;
    }
    int count = 0;
    int left = 0;
    int right = numsSize - 1;
    int mid = left + (right - left) / 2;
    //缩小双边界
    while (nums[right] > target && left < right && mid>0)
    {
        if (nums[left] < target)
        {
            left++;
        }
        if (nums[mid] > target)
        {
            right = mid - 1;
            mid = left + (right - left) / 2;
        }
        else
        {
            right--;
        }
    }
    //查找
    for (int i = left; i <= right; i++)
    {
        if (nums[i] == target)
        {
            count++;
        }
    }
    return count;
}


//版本二
int search(int* nums, int numsSize, int target)
{
    if (numsSize == 0)
    {
        return 0;
    }
    int count = 0;
    int left = 0;
    int right = numsSize - 1;
    int mid = left + (right - left) / 2;
    //缩小双边界
    while (nums[right] > target &&nums[left]<target&& left < right && mid>0)
    {
        //调整右边界
        if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else
        {
            right--;
        }
        //调整左边界
        if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            left++;
        }

    }
    //查找
    for (int i = left; i <= right; i++)
    {
        if (nums[i] == target)
        {
            count++;
        }
    }
    return count;
}